W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Armia Bajtocka planuje przeprowadzić wspólnie z Armią Bitocką wielkie manewry wojskowe. Manewry odbędą się na poligonie w Bajtowie Pomorskim. Poligon jest oficerom dobrze znany, jednak nie wiedzą oni dokładnie, jakie zadania przyjdzie im wypełniać. Dlatego właśnie zwrócili się do Ciebie, rekrucie, z "uprzejmą" prośbą.
Twoi przełożeni znają dokładny rozkład obiektów strategicznych znajdujących się na poligonie. W czasie manewrów wielokrotnie będą musieli atakować różne obszary poligonu. W szczególności, jedną z kluczowych decyzji będzie właściwe dobranie wielkości sił przeznaczonych do ataku - siły te powinny być adekwatne do potrzeb, czyli proporcjonalne do liczby obiektów strategicznych we wnętrzu atakowanego obszaru. Twoim zadaniem będzie określenie dla każdego obszaru, reprezentowanego jako wielokąt o wierzchołkach w obiektach strategicznych, ile obiektów strategicznych znajduje się ściśle wewnątrz niego.
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite: (), oznaczająca liczbę obiektów znajdujących się na poligonie, oraz (), oznaczająca liczbę zapytań. Obiekty są ponumerowane od do .
W kolejnych wierszach znajduje się par liczb całkowitych (), oznaczających współrzędne -tego obiektu. Żadne trzy obiekty nie leżą na jednej prostej.
W kolejnych wierszach znajduje się opisów zapytań. Każdy taki opis rozpoczyna się od liczby określającej liczbę wierzchołków wielokąta (). Dalej następuje różnych liczb całkowitych z przedziału oznaczających numery obiektów strategicznych będących kolejnymi wierzchołkami wielokąta. Żaden z podanych wielokątów nie będzie miał samoprzecięć, a wierzchołki wielokątów będą podane zgodnie z kierunkiem ruchu wskazówek zegara. Suma wszystkich liczb nie przekroczy .
Twój program powinien wypisać na standardowe wyjście wierszy zawierających odpowiedzi na kolejne zapytania. Odpowiedzią dla jednego zapytania jest liczba obiektów strategicznych znajdujących się wewnątrz podanego wielokąta.
Dla danych wejściowych:
6 4 0 0 0 5 5 0 11 10 5 5 2 1 4 1 2 4 3 4 1 2 5 3 3 6 2 4 3 1 2 6
poprawną odpowiedzią jest:
2 1 1 0
Kółka na rysunku reprezentują obiekty strategiczne, a liczby przy kółkach - ich numery.
Na rysunku zaznaczono obszary z pierwszego (linie ciągłe) i trzeciego (linie przerywane,
zamalowany na żółto) zapytania.
Autor zadania: Michał Pilipczuk.